/**
 * created by lpw
 */
public class TestClass {

    public static void main(String[] args) {
        TreeNode treeNode = creatTreeNode();
        List<Double> doubles = averageOfLevels(treeNode);
        StringBuilder sb=new StringBuilder("[");
        for (Double d:doubles) {
            sb.append(d);
            sb.append(",");
        }
        sb.replace(sb.length()-1,sb.length(),"]");
        System.out.println(sb.toString());
    }

    public static List<Double> averageOfLevels(TreeNode treeNode){
        List<Double> result=new ArrayList<>();
        if(treeNode==null) return result;
        //用于记录每一层的TreeNode
        List<TreeNode> nodeList=new ArrayList();
        nodeList.add(treeNode);
        while (!nodeList.isEmpty()){
            //用于记录下一层的TreeNode
            List<TreeNode> nextList=new ArrayList();
            //自增的，用于记录每一层的个数
            int count=0;
            //用于记录每一层的数字之和
            double sum=0;
            for(TreeNode curNode:nodeList){
                sum+=curNode.value;
                count++;
                if(curNode.left!=null) nextList.add(curNode.left);
                if(curNode.right!=null) nextList.add(curNode.right);
            }
            double average=sum/count;
            result.add(average);
            nodeList=nextList;
        }
        return result;
    }

    public static TreeNode creatTreeNode(){
        //｛1, 2 ,3, 4,5, null, 6｝
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(5);
        TreeNode treeNode6=new TreeNode(6);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.right=treeNode6;
        return treeNode1;
    }

    public static class TreeNode {
        int value;
        TreeNode  left;
        TreeNode  right;
        public TreeNode(int value) {
            this.value = value;
        }
    }
}